package queenChessProblem;

import java.util.List;

import utils.RandomGenerator;
import genetic_algorithm.Chromosome;
import genetic_algorithm.Mutation;

/**
 * Implements mutation phase for the genetic algorithm to solve the queens problem.
 * A mutation is choosing a new random position for the queens which has the most collisions
 */
public class QueensMutation implements Mutation {

	@Override
	public void mutate(List<Chromosome> chromosomes, double rate) {
		int index, x;
		for (Chromosome chrom : chromosomes) {

			int chance = RandomGenerator.nextInt(1000);
			if ((chance / 1000.0) < rate) {
				index = findWorstQueen(chrom);
				x = RandomGenerator.nextInt(8);
				chrom.setValue(index, x);
			}
		}
	}

	public int findWorstQueen(Chromosome chrom) {
		
		List<Object> queens = chrom.getAllValues();
		int currPenalty = 0; // penalty of current position
		int result = -1; // index of worst position		
		int maxPenalty = 0; // maximal penalty so far
		int col1 = 0, col2 = 0; // columns of positions being compared
		for (int row1 = 0; row1 < 8; ++row1) {
			for (int row2 = 0; row2 < 8; ++row2) {

				// do not compare the same position
				if (row1 == row2) {
					continue;
				}

				// extract columns
				col1 = (Integer) queens.get(row1);
				col2 = (Integer) queens.get(row2);

				// check if on same column or same diagonal
				if (col1 == col2 || Math.abs((row1 - row2)) == Math.abs((col1 - col2))) {
					++currPenalty;
				}
			}

			// update worst position
			if (currPenalty > maxPenalty) {
				maxPenalty = currPenalty;
				result = row1;
			}

			// reset penalty for next iteration
			currPenalty = 0;
		}

		// if chromosome has no conflicts, choose a position in random
		return (result == -1) ? RandomGenerator.nextInt(chrom.getAllValues()
				.size()) : result;
	}
}
